#include "PageCache.h"

PageCache PageCache::s_inst;

Span *PageCache::NewSpan(size_t k)
{
    assert(k > 0);
    std::unique_lock<std::recursive_mutex> lock(_rmtx);
    // 如果k>=NPAGES，就直接向堆申请（PageCache无法管理）
    if (k >= NPAGES)
    {
        void *mem = SystemAlloc(k);
        Span *newSpan = _spanPool.New();
        newSpan->_pageId = (pageid_t)mem >> PAGE_SHIFT;
        newSpan->_pageNum = k;
        newSpan->_isUse = true;
        // _idSpanMap[newSpan->_pageId] = newSpan;
        _idSpanMap.set(newSpan->_pageId, newSpan);
        return newSpan;
    }

    assert(k < NPAGES);

    // 检查对应的桶(spanlist)是否为空，如果不为空，则返回其中一个span
    if (!_spanLists[k].Empty())
    {
        Span *kspan = _spanLists[k].PopFront();
        // 建立pageid与kspan的映射关系
        for (int i = 0; i < kspan->_pageNum; ++i)
        {
            // _idSpanMap[i + kspan->_pageId] = kspan;
            _idSpanMap.set(i + kspan->_pageId, kspan);
        }
        kspan->_isUse = true;
        return kspan;
    }

    // 如果为空，则继续在哈希表中查找更大页空间的内存，找到一个不为空的桶，将其span分裂成两个小span
    for (int i = k + 1; i < NPAGES; ++i)
    {
        if (!_spanLists[i].Empty())
        {
            Span *kspan = _spanPool.New();
            Span *nspan = _spanLists[i].PopFront();

            // size_t tmp = nspan->_pageNum; // debug

            // 把nspan头部的前k页切给kspan
            kspan->_pageId = nspan->_pageId;
            kspan->_pageNum = k;
            kspan->_isUse = true;
            nspan->_pageId = nspan->_pageId + k;
            nspan->_pageNum = nspan->_pageNum - k;

            // 建立kspan中所有页的页号与其所属span地址的映射
            for (int i = 0; i < kspan->_pageNum; ++i)
            {
                // _idSpanMap[i + kspan->_pageId] = kspan;
                _idSpanMap.set(i + kspan->_pageId, kspan);
            }

            // 挂接在PageCache中的span只映射首页和尾页即可
            // _idSpanMap[nspan->_pageId] = nspan;
            // _idSpanMap[nspan->_pageId + nspan->_pageNum - 1] = nspan;
            _idSpanMap.set(nspan->_pageId, nspan);
            _idSpanMap.set(nspan->_pageId + nspan->_pageNum - 1, nspan);

            // 把切剩下的nspan挂接到对应的spanlist当中
            _spanLists[nspan->_pageNum].PushFront(nspan);

            // cout << std::this_thread::get_id() << " seperate!" << " before seperate npage: " << tmp
            //      << " after pair <" << kspan->_pageNum << "&" << nspan->_pageNum << ">" << endl; // debug
            return kspan;
        }
    }

    // 如果一直找到128号桶都为空，则需要向内存申请128页（1MB）的空间挂到128号桶，再递归调用自己(重新分裂)
    void *mem = SystemAlloc(NPAGES - 1); // NPAGES可以根据需求调整，不一定就是128
    Span *newSpan = _spanPool.New();
    newSpan->_pageId = (pageid_t)mem >> PAGE_SHIFT;
    newSpan->_pageNum = NPAGES - 1;
    _spanLists[NPAGES - 1].PushFront(newSpan);

    return NewSpan(k);
}

Span *PageCache::MapObjectToSpan(void *obj)
{
    pageid_t id = (pageid_t)obj >> PAGE_SHIFT;
    // std::unique_lock<std::recursive_mutex> lock(_rmtx);
    // auto ret = _idSpanMap.find(id);
    // if (ret == _idSpanMap.end())
    // {
    //     assert(false);
    //     return nullptr;
    // }

    Span *ret = static_cast<Span *>(_idSpanMap.get(id));
    assert(ret != nullptr);
    return ret;
}

void PageCache::ReleaseSpanToPageCache(Span *span)
{
    std::unique_lock<std::recursive_mutex> lock(_rmtx);
    if (span->_pageNum >= NPAGES)
    {
        void *mem = (void *)(span->_pageId << PAGE_SHIFT);
        SystemDealloc(mem, span->_pageNum);
        _spanPool.Delete(span);
        return;
    }
    // 向前合并<-
    while (true)
    {
        // 先找前一页，看归属于哪个span
        pageid_t prevId = span->_pageId - 1;
        // Span *prevSpan = nullptr;
        // if (_idSpanMap.find(prevId) != _idSpanMap.end())
        //     prevSpan = _idSpanMap[prevId];

        Span *prevSpan = static_cast<Span *>(_idSpanMap.get(prevId));
        // 检查是否满足合并条件
        if (!CanMerge(span, prevSpan))
            break;

        // 合并
        // size_t tmp = span->_pageNum; // debug
        span->_pageId = prevSpan->_pageId;
        span->_pageNum += prevSpan->_pageNum;
        _spanLists[prevSpan->_pageNum].Erase(prevSpan);
        // cout << std::this_thread::get_id() << " backward merge! pair: <"
        //      << prevSpan->_pageNum << "&" << tmp
        //      << "> after merge npage: " << span->_pageNum << endl; // debug
        _spanPool.Delete(prevSpan);
    }

    // 向后合并->
    while (true)
    {
        // 先找后一页，看归属于哪个span
        pageid_t nextId = span->_pageId + span->_pageNum;
        // Span *nextSpan = nullptr;
        // if (_idSpanMap.find(nextId) != _idSpanMap.end())
        //     nextSpan = _idSpanMap[nextId];

        Span *nextSpan = static_cast<Span *>(_idSpanMap.get(nextId));
        // 检查是否满足合并条件
        if (!CanMerge(span, nextSpan))
            break;

        // 合并
        // size_t tmp = span->_pageNum; // debug
        span->_pageNum += nextSpan->_pageNum;
        _spanLists[nextSpan->_pageNum].Erase(nextSpan);
        // cout << std::this_thread::get_id() << " forward merge! pair: <"
        //      << tmp << "&" << nextSpan->_pageNum
        //      << "> after merge npage: " << span->_pageNum << endl; // debug
        _spanPool.Delete(nextSpan);
    }

    // 挂接到对应的桶，并建立首尾页号与span指针的映射
    _spanLists[span->_pageNum].PushFront(span);
    // _idSpanMap[span->_pageId] = span;
    // _idSpanMap[span->_pageId + span->_pageNum - 1] = span;
    _idSpanMap.set(span->_pageId, span);
    _idSpanMap.set(span->_pageId + span->_pageNum - 1, span);
    span->_isUse = false;
}

inline bool PageCache::CanMerge(Span *span, Span *target)
{
    if (target != nullptr && !target->_isUse && (target->_pageNum + span->_pageNum < NPAGES))
        return true;
    else
        return false;
}